package leetcode.editor.cn.q1_300.q200;
//给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [3,1,4,null,2], k = 1
//输出：1
// 
//
// 示例 2： 
// 
// 
//输入：root = [5,3,6,2,4,null,null,1], k = 3
//输出：3
// 
//
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数为 n 。 
// 1 <= k <= n <= 10⁴ 
// 0 <= Node.val <= 10⁴ 
// 
//
// 
//
// 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？ 
//
// 👍 733 👎 0

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 中序遍历第 k 个元素
 * <p>
 * 执行耗时:0 ms,击败了100.00% 的Java用户
 * 内存消耗:43.2 MB,击败了5.42% 的Java用户
 */
public class Q230_KthSmallestElementInABst {
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public int kthSmallest(TreeNode root, int k) {

            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;

            pushStack(node, stack);

            int num = 0;
            while (k != 0) {
                TreeNode cur = stack.pop();
                if (cur.right != null) {
                    pushStack(cur.right, stack);
                }
                num = cur.val;
                k--;
            }
            return num;
        }

        public void pushStack(TreeNode node, Deque<TreeNode> stack) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q230_KthSmallestElementInABst().new Solution();
        // TO TEST
        System.out.println(solution.kthSmallest(BTreeUtil.generateFromArr(3, 1, 4, null, 2), 1));
        System.out.println(solution.kthSmallest(BTreeUtil.generateFromArr(5, 3, 6, 2, 4, null, null, 1), 3));
    }
}